Min stack

Time: O(N); Space: O(1); easy

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time: * push(x) – Push element x onto stack * pop() – Removes the element on top of the stack * top() – Get the top element * getMin() – Retrieve the minimum element in the stack

Example 1:

Input: [“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]

[[],[-2],[0],[-3],[],[],[],[]]

Output: [null,null,null,null,-3,null,0,-2]

Explanation:

minStack = MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin(); // return -3

minStack.pop();

minStack.top(); // return 0

minStack.getMin(); // return -2

Constraints:

  • Methods pop, top and getMin operations will always be called on non-empty stacks.

Hints:

  1. Consider each node in the stack having a minimum value.

[1]:

class MinStack1(object):
    def __init__(self):
        self.min = None
        self.stack = []

    def push(self, x) -> int:
        '''
        :type x: int
        :rtype: int
        '''
        if not self.stack:
            self.stack.append(0)
            self.min = x
        else:
            self.stack.append(x - self.min)
            if x < self.min:
                self.min = x

    def pop(self):
        x = self.stack.pop()
        if x < 0:
            self.min = self.min - x

    def top(self) -> int:
        x = self.stack[-1]
        if x > 0:
            return x + self.min
        else:
            return self.min

    def getMin(self) -> int:
        return self.min

[6]:

stack = MinStack1()
stack.push(-2)
stack.push(0)
stack.push(-3)
assert stack.getMin() == -3
stack.pop()
stack.top()
assert stack.getMin() == -2

[7]:

class MinStack2(object):
    '''
    Time: O(N); Space: O(N)
    '''
    def __init__(self):
        self.stack, self.minStack = [], []

    def push(self, x) -> int:
        '''
        :type x: int
        :rtype: int
        '''
        self.stack.append(x)
        if len(self.minStack):
            if x < self.minStack[-1][0]:
                self.minStack.append([x, 1])
            elif x == self.minStack[-1][0]:
                self.minStack[-1][1] += 1
        else:
            self.minStack.append([x, 1])

    def pop(self):
        x = self.stack.pop()
        if x == self.minStack[-1][0]:
            self.minStack[-1][1] -= 1
            if self.minStack[-1][1] == 0:
                self.minStack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.minStack[-1][0]

stack = MinStack2() stack.push(-2) stack.push(0) stack.push(-3) assert stack.getMin() == -3 stack.pop() stack.top() assert stack.getMin() == -2